LeetCode 16. 3Sum Closest

发表于 | 分类于

好久没写C的，写个C复习一下，写个简单的leetcode吧

  1. 3Sum Closest
    Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

这个问题比较简单，我先写了个暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int threeSumClosest(int* nums, int numsSize, int target) {
    int result=nums[0] + nums[1] + nums[2];
    int i, j, k;
    int sum;
    
    for(i=0; i<numsSize-2; i++)
    {
        for(j=i+1; j<numsSize-1; j++)
        {
            for(k=j+1; k<numsSize; k++)
            {
                sum = nums[i] + nums[j] + nums[k];
                if(abs(sum-target) <= abs(result-target))
                    result = sum;
            }
        }
    }
    
    return result;
}

runtime为172 ms可想而知是很低的。

看了下别人的solution，先排序再算要快好多，于是我先尝试了

冒泡排序

1
2
3
4
5
6
7
8
9
10
void bubble_sort(int arr[], int len) {
    int i, j, temp;
    for (i = 0; i < len - 1; i++)
        for (j = 0; j < len - 1 - i; j++)
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
}

Runtime 为8 ms，还是差点，仔细看了下，因该是我的排序算法慢了，看到别人的solution用c中的快排qsort()，可惜我之前没学过这个函数,所以没想到，赶紧恶补下。

原文地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void qsort(
    void *base,
    size_t nmemb,
    size_t size,
    int (*compar)(const void *, const void *)
    );
    
函数功能：qsort()函数的功能是对数组进行排序，数组有nmemb个元素，每个元素大小为size。

参数base       - base指向数组的起始地址，通常该位置传入的是一个数组名
参数nmemb  - nmemb表示该数组的元素个数
参数size        - size表示该数组中每个元素的大小（字节数）
参数(*compar)(const void *, const void *) - 此为指向比较函数的函数指针，决定了排序的顺序。

函数返回值：无

注意：如果两个元素的值是相同的，那么它们的前后顺序是不确定的。也就是说qsort()是一个不稳定的排序算法。

compar参数
compar参数指向一个比较两个元素的函数。比较函数的原型应该像下面这样。注意两个形参必须是const void *型，同时在调用compar 函数（compar实质为函数指针，这里称它所指向的函数也为compar）时，传入的实参也必须转换成const void *型。在compar函数内部会将const void *型转换成实际类型，见下文。

int compar(const void *p1, const void *p2);
如果compar返回值小于0（< 0），那么p1所指向元素会被排在p2所指向元素的前面
如果compar返回值等于0（= 0），那么p1所指向元素与p2所指向元素的顺序不确定
如果compar返回值大于0（> 0），那么p1所指向元素会被排在p2所指向元素的后面
因此，如果想让qsort()进行从小到大（升序）排序，那么一个通用的compar函数可以写成这样：

int compareMyType (const void * a, const void * b)
{
   if ( *(MyType*)a <  *(MyType*)b ) return -1;
   if ( *(MyType*)a == *(MyType*)b ) return 0;
   if ( *(MyType*)a >  *(MyType*)b ) return 1;
}

注意：你要将MyType换成实际数组元素的类型。

使用快排后

Runtime: 4 ms, faster than 100.00% of C online submissions for 3Sum Closest.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int comp(const void*a,const void*b)
{
    return *(int*)a-*(int*)b;
}

int threeSumClosest(int* nums, int numsSize, int target) 
{
    int result=nums[0] + nums[1] + nums[2];
    
    if(numsSize <= 3)
        return result;
    
    int i, j, k;
    int sum;
    
    qsort(nums, numsSize, sizeof(int), comp);
        
    for(i=0; i<numsSize-2; i++)
    {
        j = i + 1;
        k = numsSize - 1;
        while(j < k)
        {
            sum = nums[i] + nums[j] + nums[k];
            if(abs(sum-target) <= abs(result-target))
            {
                if(sum == target)
                    return sum;
                result = sum;   
            }
            (sum > target)? k--: j++;
        }
    }
    
    return result;
}
0%